# cw.mod    
# by Yu Liu, 09/2001.   Based on arcflow.mod and cisco.mod
# Arc-flow model for spare capacity allocation

### 1. given parameters involved in the models

set NODES;  # each node has a unique name (key)

set LINKS;  # a link has a unique name (key) to identify parallel links
param lo {LINKS} symbolic in NODES;  # source node of a link
param ld {LINKS} symbolic in NODES;  # sestination node of a link
param cost {LINKS} default 1 >= 0; # link cost can be distance, delay..
param capacity {LINKS} default Infinity >= 0; # residual capacity

set FLOWS;  # each flow has a unique name (key)
param fo {FLOWS} symbolic in NODES;  # source node of a flow
param fd {FLOWS} symbolic in NODES;  # destination node of a flow
param M {FLOWS} default 1 >=0;  # Flow demands, can be float number

set FAILS;  # each failure scenario has its unique label (key)

# inter-set matrices

# node-link incident matrix B
param B {NODES,LINKS} integer default 0 >= -1 <= 1;  
check {i in LINKS}: sum {n in NODES} B[n,i] = 0;

# flow-node incident matrix
param D {FLOWS, NODES} integer default 0 >= -1 <= 1; 
check {r in FLOWS}: sum {n in NODES} D[r,n] = 0;

# failure link incident matrix
param F {FAILS, LINKS} binary default 0;  

### 2. find routes for working paths

param P {FLOWS, LINKS} binary default 0;  # working path-link incident matrix
param w {LINKS} default 0;    # link capacity used for working routes
check {i in LINKS}: w[i] = sum{ r in FLOWS} P[r, i] * M[r];

var YP {FLOWS} binary default 1;  # indicate this flow can be routed or not
var alpha default 1.0 >= 0 <= 1.0;      # maximum link utilization

s.t. working_route {r in FLOWS, n in NODES}:
  sum {i in LINKS} P[r,i] * B[n,i] = D[r,n] * YP[r];
# Flow conservation constraints in matrix format 

s.t. working_aggr {i in LINKS}:
  w[i] = sum{ r in FLOWS} P[r, i] * M[r];
# calculate link capacity used for all routes

s.t. working_limit { i in LINKS}:
  w[i] <= capacity[i] * alpha ;
# limits each link under certain utilization

## several different objectives in this case.

# minimize the total capacity used in the network
minimize total_work:  sum {i in LINKS} cost[i]* w[i];
#problem min_total_work:  total_work, 
#  working_route, working_aggr, working_limit, P, w;

# minimize the maximum utilization of all links
#minimize max_util: alpha;
#problem min_max_util: max_util, working_route, working_aggr, 
#  working_limit, P, w, alpha;

# max total routed flow 
#minimize unrouted_flow: sum {r in FLOWS} (1-YP[r]);
#problem mx_rt_flow: unrouted_flow, working_route, working_aggr, 
#  working_limit, P, w, YP;  

# objective can be others like:
# maximize routed_load: sum {r in FLOWS} YP[r]*M[r];
# or
# param c >=0 default 1.0;
# maximize routed_flow_balance: sum {r in FLOWS} YP[r] - c * alpha;


### 3. Spare capacity allocation and backup path routing

# flow failure incident matrix
param U {r in FLOWS, k in FAILS} binary default (max{i in LINKS} P[r,i]*F[k,i]);
# flow tabu-link incident matrix
param T {r in FLOWS, i in LINKS} binary default (max{k in FAILS} U[r,k]*F[k,i]);

var Q {FLOWS, LINKS} binary default 0;  
var G {LINKS, FAILS} default 0 >= 0;
var s {LINKS} default 0;   # can be float number
var YQ {FLOWS} binary default 1;  # indicate this flow can be routed or not

# Flow convervation constraints in matrix format 
s.t. flow_csv_backup {r in FLOWS, n in NODES}:
  sum {i in LINKS} Q[r,i] * B[n,i] = D[r,n] * YQ[r];

# calculate link capacity used for all routes
s.t. cap_aggr_spare {i in LINKS, k in FAILS}:
  s[i] >= G[i, k];

# limits each link under certain utilization
s.t. cap_limit_spare { i in LINKS}:
  s[i] + w[i] <= capacity[i] * alpha;

# find spare provision matrix G = Q^T . M . U
s.t. spare_prov {i in LINKS, k in FAILS}:
  G[i,k] = sum{ r in FLOWS} G[r,i] * M[r] * U[r,k] ;

# make sure backup path are disjointed from working path.
s.t. disjoint_path {i in LINKS, r in FLOWS}:
  T[r,i] + Q[r,i] <= 1;

# following two prepares the constants for spare provision matrix G
#s.t. find_U {r in FLOWS, k in FAILS}: 
#  U[r,k] = sum {i in LINKS} P[r,i] * F[k,i];
#s.t. find_T {r in FLOWS, i in LINKS}: 
#  T[r,i] = sum {k in FAILS} U[r,k] * F[k,i];

minimize spare_cost: sum {i in LINKS } cost[i] * s[i];

problem find_spare:
 spare_cost,  flow_csv_backup, cap_aggr_spare, cap_limit_spare, spare_prov,
  disjoint_path, Q, G, s;

